package negocios;
import java.io.Serializable;
//import java.security.InvalidParameterException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.TreeSet;


public class Grafo <T> implements Serializable {
	
	private ArrayList<T>vertices;
	private ArrayList<TreeSet<T>>vecinos;
	private static final long serialVersionUID = 1L;
	
	
	public Grafo (){
		vertices = new ArrayList<T>();
		vecinos = new ArrayList<TreeSet<T>>();
	}
	
	public int getCantidadDeVertices(){
		return vertices.size();
	}
	
	public void agregarVertice(T obj){
		vertices.add(obj);
		vecinos.add(iesimoVertice(obj), new TreeSet<T>());
	}
	
	public void agregarArista(T obj1, T obj2){

		vecinos.get(iesimoVertice(obj1)).add(obj2);
		vecinos.get(iesimoVertice(obj2)).add(obj1);
		
	}
	
	public  int iesimoVertice(T obj) {
		return vertices.indexOf(obj); 
	}
	
	public void borrarArista(T obj1, T obj2){

		vecinos.get(iesimoVertice(obj1)).remove(obj2);
		vecinos.get(iesimoVertice(obj2)).remove(obj1);
		
	}
	
	
	public boolean sonVecinos(T obj1, T obj2){
		
		boolean ret = (pertenece(obj1) && pertenece(obj2)) ? 
				vecinos.get(iesimoVertice(obj1)).contains(obj2): false;
		return ret;
	}
	
	public int grado(T obj){
		return vecinos.get(iesimoVertice(obj)).size();
	}
	
	public TreeSet<T> losVecinos(T obj){
		return vecinos.get(iesimoVertice(obj));
		
	}
	
	public void eliminarVertice(T obj){

		for(int i = 0; i < vertices.size(); i++){
			if(vecinos.get(i).contains(obj)){
				vecinos.get(i).remove(obj);
			}
		}
		vecinos.get(iesimoVertice(obj)).remove(obj);
		vertices.remove(obj);
	}
	
	public boolean pertenece(T obj){
		 return vertices.contains(obj);
	}
	
	public T getVertice(int indice ){
		return vertices.get(indice);
	}
	
	
	public ArrayList<TreeSet<T>> getVecinos() {
		return vecinos;
	}

	private boolean[] BFS(T origen){
		
		Queue<T> cola = new LinkedList<T>();
		boolean[] marcado = new boolean [getCantidadDeVertices()];
		marcado[iesimoVertice(origen)] = true;
		
		cola.offer(origen);
		while(!cola.isEmpty()){
			T vert = cola.poll();
			for(T v : losVecinos(origen) ){
				if (marcado[iesimoVertice(v)] == false){
					cola.add(v);		
				}
				marcado[iesimoVertice(vert)]=true;
			}
		}
		return marcado;
	}

	public boolean esConexo(T origen){
		boolean ret = true;
		boolean [] array = BFS(origen);

		for(int i = 0; i < array.length; i++){
			if(array[i]==false){
				ret = false;
			}
		}
		return true && ret;
	}
	

	public ArrayList<T> todosLosVertices(){
		return this.vertices;
	}

}
